package developer.算法.回溯.组合总和;

import java.util.*;

/**
 * @author zhangyongkang
 * @time 2025/4/1 17:05
 * @description 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * <p>
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * <p>
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 * 解释：
 * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 * 7 也是一个候选， 7 = 7 。
 * 仅有这两种组合。
 * 示例 2：
 * <p>
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 * 示例 3：
 * <p>
 * 输入: candidates = [2], target = 1
 * 输出: []
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= candidates.length <= 30
 * 2 <= candidates[i] <= 40
 * candidates 的所有元素 互不相同
 * 1 <= target <= 40
 */
public class ZuHeZongHe {

    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        List<List<Integer>> lists = solution.combinationSum(
                new int[]{2, 3, 5},
                8
        );
        for (List<Integer> list : lists) {
            System.out.println("");
            list.forEach(System.out::print);
        }
    }


    static class Solution3 {
        private List<List<Integer>> result;

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            result = new ArrayList<>();
            List<Integer> total = new ArrayList<>(candidates.length);
            for (int candidate : candidates) {
                total.add(candidate);
            }

            dfs(
                    target,
                    0,
                    candidates,
                    new ArrayList<>()
            );

            return result;
        }

        private void dfs(
                int target,
                int idx,
                int[] candidates,
                List<Integer> current
        ) {
            if (idx == candidates.length) {
                return;
            }
            if (target == 0) {
                result.add(new ArrayList<>(current));
                return;
            }

            //忽略当前情况，直接进行dfs
            dfs(target, idx + 1, candidates, current);

            //不忽略当前情况
            if (target - candidates[idx] >= 0) {
                current.add(candidates[idx]);
                dfs(target - candidates[idx], idx, candidates, current);
                current.remove(current.size() - 1);
            }

        }
    }

    static class Solution {
        Map<String, List<Integer>> result;

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            result = new HashMap<>();
            dfs(target, new ArrayList<>(), candidates);
            return new ArrayList<>(result.values());
        }

        private void dfs(int target, List<Integer> current, int[] candidates) {
            int currentVal = 0;
            for (Integer i : current) {
                currentVal += i;
            }
            if (currentVal == target) {
                List<Integer> currentSort = new ArrayList<>(current);
                Collections.sort(currentSort);
                String key = "";
                for (int i = 0; i < currentSort.size(); i++) {
                    key += currentSort.get(i);
                }
                result.put(key, currentSort);
                return;
            } else if (currentVal > target) {
                return;
            }

            for (int candidate : candidates) {
                current.add(candidate);
                dfs(target - candidate, current, candidates);
                current.remove(current.size() - 1);
            }
        }
    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/combination-sum/solutions/406516/zu-he-zong-he-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class SolutionOfficial {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> combine = new ArrayList<Integer>();
            dfs(candidates, target, ans, combine, 0);
            return ans;
        }

        public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
            if (idx == candidates.length) {
                return;
            }
            if (target == 0) {
                ans.add(new ArrayList<Integer>(combine));
                return;
            }
            // 直接跳过
            dfs(candidates, target, ans, combine, idx + 1);
            // 选择当前数
            if (target - candidates[idx] >= 0) {
                combine.add(candidates[idx]);
                dfs(candidates, target - candidates[idx], ans, combine, idx);
                combine.remove(combine.size() - 1);
            }
        }
    }

}
